package net.blank.world.aStar
{
	import net.blank.world.aStar.BHeaps.BHeapForMin;
	
	/**
	 * A星寻路(基于最小二叉堆)
	 * @author blank
	 * 
	 */
	final public class AStar
	{
		/**直角移动的Cost值*/
		public static const STRAIGHT_COST:int=100;
		
		/**对角移动的Cost值*/
		public static const DIAG_COST:int=140;
		
		/**直角移动的Cost值的十分之一*/
		public static const STRAIGHT_COST_DIVIDE10:int=10;
		
		/**对角移动的Cost值的十分之一*/
		public static const DIAG_COST_DIVIDE10:int=14;
		
		/**地图节点*/
		private var _nodes:Vector.<Vector.<Node>>;
		
		/**地图的宽度(列数)*/
		private var _numCols:int;
		
		/**地图的高度(行数)*/
		private var _numRows:int;
		
		/**当前节点到结束节点的估价函数*/
		private var _heuristic:Function;
		
		/**当前的寻路编号*/
		private var searchPathCheckNum:int;
		
		/**当前查找可移动范围的编号*/
		private var walkableRangeCheckNum:int;
		
		/**是否是四向寻路,默认为八向寻路*/
		private var _isFourWay:Boolean;
		
		/**
		 * 存放"openList"的最小二叉堆
		 */
		private var minBinaryHeapForOpenList:BHeapForMin;
		
		/**
		 * 曼哈顿启发函数<br/>
		 * 用此启发函数在八向寻路中找到的并不是最优路径,因为它的运算结果可能远远大于开始结点到目标结点的距离,
		 * 但是此启发函数的运算速度非常快
		 * @param x1 节点1x
		 * @param y1 节点1y
		 * @param x2 节点2x
		 * @param y2 节点2y
		 * @return 
		 * 
		 */
		public static function manhattan(x1:int,y1:int,x2:int,y2:int):int{
			return (
				(x1 > x2 ? x1 - x2 : x2 - x1)
				+
				(y1 > y2 ? y1 - y2 : y2 - y1)
			) * STRAIGHT_COST;
		}
		
		/**
		 * 对角线启发函数<br/>
		 * 此启发函数比较精确,计算的代价比 欧拉启发函数 低
		 * @param x1 节点1x
		 * @param y1 节点1y
		 * @param x2 节点2x
		 * @param y2 节点2y
		 * @return 
		 * 
		 */
		public static function diagonal(x1:int,y1:int,x2:int,y2:int):int{
			var dx:int = x1 > x2 ? x1 - x2 : x2 - x1;
			var dy:int = y1 > y2 ? y1 - y2 : y2 - y1;
			
			return dx > dy ? DIAG_COST * dy + STRAIGHT_COST * (dx - dy) : DIAG_COST * dx + STRAIGHT_COST * (dy - dx);
		}
		
		/**
		 * 获取节点
		 * @param word_x
		 * @param word_y
		 * @return 
		 * 
		 */
		public function getNode(word_x:int,word_y:int):Node{
			if(
				(-1<word_x && word_x<_numCols) 
				&& 
				(-1<word_y && word_y<_numRows)
			){
				return _nodes[word_x][word_y];
			}
			return null;
		}
		
		/**
		 * 获取节点的相邻节点
		 * @param node
		 * @return 
		 * 
		 */
		private function getAdjacentNodes(node:Node):Vector.<Node>{
			var adjacentNodes:Vector.<Node>=new Vector.<Node>();
			
			var startX:int,endX:int,startY:int,endY:int;
			
			startX=Math.max(0,node._world_x-1);
			endX=Math.min(_numCols-1,node._world_x+1);
			
			startY=Math.max(0,node._world_y-1);
			endY=Math.min(_numRows-1,node._world_y+1);
			
			var testNode:Node;
			for(var i:int=startX;i<=endX;i++){
				for(var j:int=startY;j<=endY;j++){
					testNode=_nodes[i][j];
					if(testNode != node){
						if(_isFourWay){
							if(!(
								i == node._world_x 
								|| 
								j == node._world_y
							)){
								continue;
							}
						}
						adjacentNodes[adjacentNodes.length]=testNode;
					}
				}
			}
			return adjacentNodes;
		}
		
		/**
		 * 刷新节点的 links 属性
		 * @param node
		 * 
		 */
		private function refreshNodeLinks(node:Node):void{
			var adjacentNodes:Vector.<Node>=getAdjacentNodes(node);
			
			var newLinks:Vector.<Link>=new Vector.<Link>();
			var cost:int;
			
			for each(var testNode:Node in adjacentNodes){
				if(testNode.walkable){
					if(
						node._world_x != testNode._world_x 
						&& 
						node._world_y != testNode._world_y
					){
						if(
							!_nodes[node._world_x][testNode._world_y].walkable 
							||
							!_nodes[testNode._world_x][node._world_y].walkable
						){
							continue;
						}else{
							cost=DIAG_COST + testNode.costMultiplier * DIAG_COST_DIVIDE10;
						}
					}else{
						cost=STRAIGHT_COST + testNode.costMultiplier * STRAIGHT_COST_DIVIDE10;
					}
					newLinks[newLinks.length]=new Link(testNode,cost);
				}
			}
			
			newLinks.fixed=true;
			
			node.links=newLinks;
		}
		
		/**
		 * 刷新节点的相邻节点的 links 属性
		 * @param node
		 * 
		 */
		private function refreshLinksOfAdjacentNodes(node:Node):void{
			var adjacentNodes:Vector.<Node>=getAdjacentNodes(node);
			
			var tn:Node;
			var links:Vector.<Link>;
			var len:int;
			var i:int;
			var cost:int;
			if(node._walkable){
				var newLinks:Vector.<Link>=new Vector.<Link>();
				for each(tn in adjacentNodes){
					links=tn.links;
					len=links.length;
					for(i=0;i<len;i++){
						if(links[i].node == node){
							if(
								node._world_x != tn._world_x 
								&& 
								node._world_y != tn._world_y
							){
								if(
									!_nodes[node._world_x][tn._world_y].walkable 
									||
									!_nodes[tn._world_x][node._world_y].walkable
								){
									continue;
								}else{
									cost=DIAG_COST + tn.costMultiplier * DIAG_COST_DIVIDE10;
								}
							}else{
								cost=STRAIGHT_COST + tn.costMultiplier * STRAIGHT_COST_DIVIDE10;
							}
							newLinks[newLinks.length]=new Link(tn,cost);
							links[i].cost=cost;
						}
					}
					
					node.links=newLinks;
				}
			}else{
				node.links=new Vector.<Link>();
				for each(tn in adjacentNodes){
					links=tn.links;
					len=links.length;
					for(i=0;i<len;i++){
						if(links[i].node == node){
							links.splice(i,1);
							break;
						}
					}
				}
			}
		}
		
		/**
		 * 刷新所有节点的 links 属性
		 * 
		 */
		private function refreshLinksOfAllNodes():void{
			for(var i:int=0;i<_numCols;i++){
				for(var j:int=0;j<_numRows;j++){
					refreshNodeLinks(_nodes[i][j]);
				}
			}
		}
		
		//public var graphics:Graphics;
		
		//public var cellSize:int;
		
		/**
		 * 搜索路径
		 * @param startNode 开始节点
		 * @param endNode 结束节点
		 * @param nowCheckNum 当前的搜索检查编号
		 * @return 
		 * 
		 */
		private function searchBaseBinaryHeap(startNode:Node,endNode:Node,nowCheckNum:uint):Boolean{
			/**已进入关闭列表(从openList中移除即进入关闭列表)*/
			const STATUS_CLOSED:uint=nowCheckNum+1;
			
			minBinaryHeapForOpenList.reset();
			var openList:BHeapForMin=minBinaryHeapForOpenList;
			
			startNode.g=0;
			startNode.f=startNode.g+_heuristic(startNode._world_x,startNode._world_y,endNode._world_x,endNode._world_y);
			startNode.searchPathCheckNum=STATUS_CLOSED;
			
			var node:Node=startNode;
			var testNode:Node;
			var f:int,g:int;
			//var n:int;
			while(node != endNode){
				var links:Vector.<Link>=node.links;
				for each(var link:Link in links){
					testNode=link.node;
					
					//graphics.drawCircle(cellSize*testNode._world_x,cellSize*testNode._world_y,2);
					
					g=node.g+link.cost;
					if(testNode.searchPathCheckNum >= nowCheckNum){/*已被检查过*/
						if(testNode.g > g){
							testNode.f=g+_heuristic(testNode._world_x,testNode._world_y,endNode._world_x,endNode._world_y);
							testNode.g=g;
							testNode.parent=node;
							
							if(testNode.searchPathCheckNum == nowCheckNum){
								openList.modify(testNode.bstNode);
							}
						}
					}else{
						testNode.f=g+_heuristic(testNode._world_x,testNode._world_y,endNode._world_x,endNode._world_y);
						testNode.g=g;
						testNode.parent=node;
						
						testNode.bstNode=openList.push(testNode);
						testNode.searchPathCheckNum=nowCheckNum;
					}
					//n++;
				}
				
				if(openList.head){
					node=openList.pop();
					
					node.searchPathCheckNum=STATUS_CLOSED;
				}else{
					return false;
				}
			}
			//trace(n);
			return true;
		}
		
		/**
		 * 寻路
		 * @param startNode 开始节点
		 * @param endNode 结束节点
		 * @return 由 Node 组成的路径数组
		 */
		public function findPath(startNode:Node,endNode:Node):Vector.<Node>{
			searchPathCheckNum += 2;
			
			if(searchBaseBinaryHeap(startNode,endNode,searchPathCheckNum)){
				var curNode:Node=endNode;
				var path:Vector.<Node>= Vector.<Node>([curNode]);
				
				var n:uint;
				while(curNode != startNode){
					curNode=curNode.parent;
					path[n++]=curNode;
				}
				return path;
			}
			return null;
		}
		
		/**
		 * 返回节点在指定的代价内可移动的范围
		 * @param startNode 开始节点
		 * @param costLimit 代价上限
		 * @return 
		 * 
		 */
		public function walkableRange(startNode:Node,costLimit:int):Vector.<Node>{
			walkableRangeCheckNum++;
			
			var maxStep:int=int(costLimit/STRAIGHT_COST);
			
			var numCols:int=_nodes.length,numRows:int=_nodes[0].length;
			
			var startX:int=Math.max(startNode._world_x-maxStep,0);
			var endX:int=Math.min(startNode._world_x+maxStep,numCols-1);
			var startY:int=Math.max(startNode._world_y-maxStep,0);
			var endY:int=Math.min(startNode._world_y+maxStep,numRows-1);
			
			var range:Vector.<Node>=new Vector.<Node>();
			
			for(var i:int=startX;i<=endX;i++){
				for(var j:int=startY;j<=endY;j++){
					var testNode:Node=_nodes[i][j];
					if(testNode.walkable){
						if(testNode.walkableRangeCheckNum != walkableRangeCheckNum){
							var path:Vector.<Node>=findPath(startNode,testNode);
							if(path && path[path.length-1].f <= costLimit){
								for each(var node:Node in path){
									if(node.walkableRangeCheckNum != walkableRangeCheckNum){
										node.walkableRangeCheckNum = walkableRangeCheckNum;
										range[range.length]=node;
									}
								}
							}
						}
					}
				}
			}
			return range;
		}
		
		/**
		 * A星寻路算法
		 * @param numCols
		 * @param numRows
		 * @param isFourWay
		 * 
		 */
		public function AStar(
			numCols:int,
			numRows:int,
			isFourWay:Boolean=false
		){
			_numCols=numCols;
			_numRows=numRows;
			
			_isFourWay=isFourWay;
			
			init();
		}
		
		/**
		 * 初始化节点的links属性
		 * 
		 */
		private function initNodeLinks():void{
			var i:int,j:int;
			
			const E_X:int=_numCols-1;
			const E_Y:int=_numRows-1;
			
			var n1:Node,n2:Node;
			
			//中间区域
			for(i=1;i<E_X;i++){
				for(j=0;j<E_Y;j++){
					n1=_nodes[i][j];
					
					n2=_nodes[i+1][j];//右方
					n1.links.push(new Link(n2,STRAIGHT_COST));
					n2.links.push(new Link(n1,STRAIGHT_COST));
					
					n2=_nodes[i][j+1];//下方
					n1.links.push(new Link(n2,STRAIGHT_COST));
					n2.links.push(new Link(n1,STRAIGHT_COST));
					
					n2=_nodes[i+1][j+1];//右下方
					n1.links.push(new Link(n2,DIAG_COST));
					n2.links.push(new Link(n1,DIAG_COST));
					
					n2=_nodes[i-1][j+1];//左下方
					n1.links.push(new Link(n2,DIAG_COST));
					n2.links.push(new Link(n1,DIAG_COST));
				}
			}
			
			//左右两边
			for(j=0;j<E_Y;j++){
				n1=_nodes[0][j];//最左边第一个元素
				
				n2=_nodes[1][j];//右方
				n1.links.push(new Link(n2,STRAIGHT_COST));
				n2.links.push(new Link(n1,STRAIGHT_COST));
				
				n2=_nodes[0][j+1];//下方
				n1.links.push(new Link(n2,STRAIGHT_COST));
				n2.links.push(new Link(n1,STRAIGHT_COST));
				
				n2=_nodes[1][j+1];//右下方
				n1.links.push(new Link(n2,DIAG_COST));
				n2.links.push(new Link(n1,DIAG_COST));
				
				n1=_nodes[E_X][j];//最右边第一个元素
				
				n2=_nodes[E_X][j+1];//下方
				n1.links.push(new Link(n2,STRAIGHT_COST));
				n2.links.push(new Link(n1,STRAIGHT_COST));
				
				n2=_nodes[_numCols-2][j+1];//左下方
				n1.links.push(new Link(n2,DIAG_COST));
				n2.links.push(new Link(n1,DIAG_COST));
			}
			
			//下边
			for(i=0;i<E_X;i++){
				n1=_nodes[i][E_Y];
				
				n2=_nodes[i+1][E_Y];//右方
				n1.links.push(new Link(n2,STRAIGHT_COST));
				n2.links.push(new Link(n1,STRAIGHT_COST));
			}
		}
		
		/**
		 * 初始化
		 * 
		 */
		private function init():void{
			_heuristic=manhattan;
			
			var node:Node;
			
			_nodes=new Vector.<Vector.<Node>>(_numCols,true);
			for(var i:int=0;i<_numCols;i++){
				_nodes[i]=new Vector.<Node>(_numRows,true);
				for(var j:int=0;j<_numRows;j++){
					node=new Node(i,j);
					node.addCallbackFunc_passCost_change(refreshLinksOfAdjacentNodes,[node]);
					
					_nodes[i][j]=node;
				}
			}
			
			initNodeLinks();
			
			minBinaryHeapForOpenList=new BHeapForMin(numCols * numRows / 2);
		}
		
		/**地图的宽度(列数)*/
		public function get numCols():int{
			return _numCols;
		}
		
		/**地图的高度(行数)*/
		public function get numRows():int{
			return _numRows;
		}
		
		/**是否是四向寻路,默认为八向寻路*/
		public function set isFourWay(value:Boolean):void{
			if(value != _isFourWay){
				_isFourWay=value;
				
				refreshLinksOfAllNodes();
			}
		}
		public function get isFourWay():Boolean{
			return _isFourWay;
		}
		
		/**当前节点到结束节点的估价函数*/
		public function set heuristic(value:Function):void{
			if(value != _heuristic){
				_heuristic=value;
			}
		}
		public function get heuristic():Function{
			return _heuristic;
		}
	}
}